﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//请你仅使用两个栈实现先入先出队列。
// 队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
//
//实现 MyQueue 类：
//
//void push(int x) 将元素 x 推到队列的末尾
//int pop() 从队列的开头移除并返回元素
//int peek() 返回队列开头的元素
//boolean empty() 如果队列为空，返回 true ；否则，返回 false
//说明：
//
//你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek / pop from top, size, 
// 和 is empty 操作是合法的。
//你所使用的语言也许不支持栈。
// 你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
//
//
//示例 1：
//
//输入：
//["MyQueue", "push", "push", "peek", "pop", "empty"]
//[[], [1], [2], [], [], []]
//输出：
//[null, null, null, 1, 1, false]
//
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);

void StackDestory(ST* ps);

void StackPush(ST* ps, STDataType x);

void StackPop(ST* ps);

STDataType StackTop(ST* ps);

bool StackEmpty(ST* ps);

int StackSize(ST* ps);

void StackInit(ST* ps)           //初始化
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)        //入栈
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)            //出栈
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}

STDataType StackTop(ST* ps)            //获取栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)         //检测栈是否为空，如果为空返回非零结果，如果不为空返回0
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)          //
{
	assert(ps);
	return ps->top;
}


typedef struct {
	ST pushST;
	ST popST;
} MyQueue;



MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&obj->pushST);
	StackInit(&obj->popST);
	return obj;
}


void myQueuePush(MyQueue* obj, int x) {
	StackPush(&obj->pushST, x);
}

void PushSTToPopST(MyQueue* obj)
{
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}
}


int myQueuePop(MyQueue* obj) {
	PushSTToPopST(obj);
	int front = StackTop(&obj->popST);
	StackPop(&obj->popST);
	return front;
}

int myQueuePeek(MyQueue* obj) {
	PushSTToPopST(obj);

	return StackTop(&obj->popST);

}

bool myQueueEmpty(MyQueue* obj) {

	return StackEmpty(&obj->popST) &&
		StackEmpty(&obj->pushST);
}

void myQueueFree(MyQueue* obj) {
	StackDestory(&obj->pushST);
	StackDestory(&obj->popST);
	free(obj);
}